package org.liaohailong.helloworld.practice;

import java.util.Stack;

/**
 * Author: liaohailong
 * Time: 2021/6/10 09:33
 * Describe: 初级算法 - 链表练习
 */
public class LinkedPractice {
    public static final class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode create(int[] arr) {
        ListNode head = null;
        ListNode node = null;
        for (int i : arr) {
            if (head == null) {
                head = new ListNode(i);
                node = head;
            } else {
                node.next = new ListNode(i);
                node = node.next;
            }
        }
        return head;
    }

    public static void print(ListNode head) {
        if (head == null) {
            System.out.println("[]");
            return;
        }
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        ListNode node = head;
        while (node != null) {
            sb.append(node.val);
            sb.append(',');
            node = node.next;
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        System.out.println(sb.toString());
    }

    // LC 删除链表中的节点
    public void deleteNode(ListNode node) {
        node.val = node.next != null ? node.next.val : 0;
        node.next = node.next != null ? node.next.next : null;
    }

    // LC 删除链表的倒数第N个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int pos = -1;
        ListNode prev = head;
        ListNode node = head;
        while (node != null) {
            pos++;
            if (node.next != null) prev = node;
            node = node.next;
        }
        int len = pos + 1;
        int index = len - n; // remove index

        // remove head of list
        if (index == 0) return head.next;
        // remove last of list
        if (index == pos) {
            prev.next = null;
            return head;
        }

        pos = -1;
        node = head;
        while (node != null) {
            pos++;
            if (pos == index) {
                // remove this node
                node.val = node.next != null ? node.next.val : 0;
                node.next = node.next != null ? node.next.next : null;
                break;
            } else node = node.next;
        }

        return head;
    }


    // LC 反转链表
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    // LC 合并两个有序链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode prev = new ListNode(-1);
        ListNode node = prev;
        ListNode n1 = l1;
        ListNode n2 = l2;
        while (n1 != null || n2 != null) {
            if (n1 != null && n2 != null) {
                if (n1.val < n2.val) {
                    node.next = n1;
                    n1 = n1.next;
                } else {
                    node.next = n2;
                    n2 = n2.next;
                }
                if (node.next != null) node = node.next;
            } else if (n1 != null && n2 == null) {
                node.next = n1;
                n1 = n1.next;
                if (node.next != null) node = node.next;
            } else if (n1 == null && n2 != null) {
                node.next = n2;
                n2 = n2.next;
                if (node.next != null) node = node.next;
            } else break;
        }

        return prev.next;
    }

    // LC 回文链表
//    public boolean isPalindrome(ListNode head) {
//        int pos = -1;
//        ListNode node = head;
//        while (node != null) {
//            pos++;
//            node = node.next;
//        }
//
//        int mid = pos / 2;
//
//        pos = -1;
//        node = head; // find the mid node
//        while (node != null) {
//            pos++;
//            if (pos == mid + 1) break;
//            node = node.next;
//        }
//
//        ListNode mirror = reverseList(node);
//
//        ListNode t1 = head;
//        ListNode t2 = mirror;
//        boolean isPalindrome = true;
//        while (t2 != null) {
//            if (t1.val != t2.val) {
//                isPalindrome = false;
//            }
//            t1 = t1.next;
//            t2 = t2.next;
//        }
//
//        // restore the list
//        reverseList(mirror);
//
//        return isPalindrome;
//    }

    // LC 回文链表
    public boolean isPalindrome(ListNode head) {
        int pos = -1;
        ListNode node = head;
        while (node != null) {
            pos++;
            node = node.next;
        }
        boolean odd = (pos + 1) % 2 == 1;
        int mid = pos / 2;

        Stack<Integer> stack = new Stack<>();
        pos = -1;
        node = head; // find the mid node
        while (node != null) {
            pos++;
            if (pos < mid) {
                stack.push(node.val);
            } else if (pos == mid) {
                if (odd) {
                    // do nothing...
                } else stack.push(node.val);
            } else {
                Integer cmp = stack.pop();
                if (cmp != node.val) return false;
            }
            node = node.next;
        }

        return true;
    }

    // LC 环形链表
//    public boolean hasCycle(ListNode head) {
//        HashSet<ListNode> set = new HashSet<>();
//        ListNode node = head;
//        while (node != null) {
//            if (set.contains(node)) return true;
//            set.add(node);
//            node = node.next;
//        }
//        return false;
//    }

    // LC 环形链表
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            if (slow == fast) return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
}
